#include <iostream>
#include <fstream>
#include <vector>
#include <cstdint>
#include <string>
#include <array>
#include <bitset>
#include <cstring>
#include <random>
#include <iomanip>
#include <optional>
#include <algorithm>
using Byte16 = std::array<uint8_t,16>;
using Node = std::pair<uint32_t,uint32_t>;//点位，原始位置
// 通用模板函数，适用于任何支持范围的容器
template <typename Container>
void printHexBytes(const Container& bytes) {
    for (const auto& byte : bytes) {
        std::cout << std::hex << std::uppercase
                  << std::setw(2) << std::setfill('0')
                  << static_cast<int>(byte) << ' ';
    }
    std::cout << std::dec << std::endl; // 重置为十进制格式
}
class FileOpenException : public std::runtime_error {
public:
    explicit FileOpenException(const std::string& message)
        : std::runtime_error(message) {}
};

class CuckooHash3{
public:
    explicit CuckooHash3(size_t NUM, float alpha = 0.5, size_t maxKicks = 500): 
        NUM(NUM),N(NUM/(3*alpha)+1), maxKicks(maxKicks),
        tables{std::vector<std::optional<Byte16>>(N),
               std::vector<std::optional<Byte16>>(N),
               std::vector<std::optional<Byte16>>(N)},
        stash{std::nullopt, std::nullopt, std::nullopt,std::nullopt},
        rng(std::random_device{}()){
                salts[0]  = 0x3F9A2C8D7E1B4A6F;
                salts[1]  = 0x8D3F2E1A9C7B4D5E;
                salts[2]  = 0x5A7C9D3F8B2E1A6D;
                }

    bool find(const Byte16& x) const {
        // 三表查找 + stash
        for (int i = 0; i < 3; i++) {
            size_t idx = hash(x, i);
            if (tables[i][idx] && (*tables[i][idx])==x) return true;
        }

        for(int i=0;i<3;i++)//第四个桶用不上
        {
            if(stash[i] && (*stash[i])==x) return true;
        }

        return false;
    }

    void insert(const Byte16& x) {
        if (find(x)) return;
        auto cur = x;
        for (size_t kick = 0; kick < maxKicks; kick++) {
            for (int i = 0; i < 3; i++) {
                size_t idx = hash(cur, i);
                if (!tables[i][idx]) {
                    tables[i][idx] = cur;
                    return;
                }
            }
            // 三处都满，随机选择一处踢出
            int i = std::uniform_int_distribution<int>(0,2)(rng);
            size_t idx = hash(cur, i);
            std::swap(cur, *tables[i][idx]);
        }
        // 踢出次数过多，放入 stash
        for(int i=0;i< 3;i++){
            if(!stash[i]){
                stash[i] = cur;
                return;
            }
        }      
        stash[3] = cur; 
        rehash();  // stash 已满则重哈希
    }
    
    size_t get_N(){
       return N*3; 
    }
        // 提供一个公共成员函数，返回 tables 的引用
    const std::vector<std::optional<Byte16>>& getTable(int index) const {
        if (index < 3) {
            return tables[index];
        }
        throw std::out_of_range("Index out of range");
    }
    const std::array<std::optional<Byte16>, 4>& getStash() const{
        return this->stash;
    }

private:
    std::mt19937 rng;//随机种子
    size_t NUM;//总元素个数
    float alpha; //负载因子本次取0.5
    size_t N, maxKicks;//需要单个hash表的元素个数，最大尝试次数
    std::vector<std::optional<Byte16>> tables[3];//三个hash表
    std::array<std::optional<Byte16>, 4> stash;//3个桶一个备用
    uint64_t salts[3];// 用于hash计算的值
  

    size_t hash(const Byte16& arr, int i) const {
            uint64_t part1 = 0;
            uint64_t part2 = 0;
            for (size_t i = 0; i < 8; ++i) {
                part1 = (part1 << 8) | arr[i];
                part2 = (part2 << 8) | arr[i + 8];
            }
            std::hash<uint64_t> hasher;
            return (hasher(part1) ^ (hasher(part2) << 1)^salts[i])%N;
    }
    
    void rehash() {
        // 扩容并重插所有元素（主表 + stash）
        size_t oldN = N;
        N *= 2;
        std::vector<std::optional<Byte16>> old0 = std::move(tables[0]);
        std::vector<std::optional<Byte16>> old1 = std::move(tables[1]);
        std::vector<std::optional<Byte16>> old2 = std::move(tables[2]);
        tables[0].assign(N, std::nullopt);
        tables[1].assign(N, std::nullopt);
        tables[2].assign(N, std::nullopt);
        std::array<std::optional<Byte16>, 4> oldStash;
        for(int i=0;i<4;i++){
            oldStash[i] = stash[i];
            stash[i].reset();
        }
        
        

        for (auto& tbl : {&old0, &old1, &old2}) {
            for (auto& o : *tbl) {
                if (o) insert(*o);
            }
        }
        
        for(int i=0;i<4;i++){
            if(oldStash[i])insert(*oldStash[i]);
        }
    }
};


void init_positionVec(std::vector<Node>& v,char* input){//初始化点位图
    std::ifstream fin(input,std::ios::binary);
    
    if(!fin.is_open()){
        throw FileOpenException("无法打开文件: " + std::string(input));
        return;
    }
    
    uint32_t cnt =0;
    uint32_t value;
    // 读取循环
    while (fin.read(reinterpret_cast<char*>(&value), sizeof(value))) {
        if(value>0){
            v.push_back(Node{cnt,value});
        }
        cnt++;
    }
    fin.close();
}

int main(int argc,char* argv[]){
    if(argc!=8){
        std::cerr<<"params error";
        return 1;
    }
 
    int binNum = std::stoi(argv[1]);//桶数，负载因子是0.5,是所以binNum会在2n
    char* position_path = argv[2];//位表
    char* t0_path =  argv[3];//
    char* P_path = argv[4];
    char* S_path = argv[5];
    char* data_path = argv[6];
    char* result_path = argv[7];
    std::vector<Node>position_Vec;
    init_positionVec(position_Vec,position_path);//初始化位表
    
    std::ifstream fin_P(P_path,std::ios::binary | std::ios::ate);
    std::ifstream fin_S(S_path,std::ios::binary | std::ios::ate);

    if(!fin_P.is_open()||!fin_S.is_open()){
        std::cerr<<"can't open file\n";
        return 1;
    }
    
    size_t sizeP = (fin_P.tellg()/16);
    size_t sizeS = (fin_S.tellg()/16);
    fin_P.clear(); // 清除 eofbit 和 failbit
    fin_P.seekg(0, std::ios::beg); // 将读取指针移动到文件开头  
    fin_S.clear(); // 清除 eofbit 和 failbit
    fin_S.seekg(0, std::ios::beg); // 将读取指针移动到文件开头  
    CuckooHash3 cuckooP(sizeP);
    CuckooHash3 cuckooS(sizeS);
    Byte16 buffer;
    uint32_t cnt = 0;
    uint32_t pointer =0;
    uint32_t maxNum = position_Vec.size(); //最大元素
    
    while (fin_P.read(reinterpret_cast<char*>(buffer.data()), buffer.size())){
        cuckooP.insert(buffer);
    }
    fin_P.close();

    while (fin_S.read(reinterpret_cast<char*>(buffer.data()), buffer.size())){
        cuckooS.insert(buffer);
    }
    fin_S.close();
    
    std::ifstream fin_t0(t0_path,std::ios::binary);
    if(!fin_t0.is_open()){
        std::cerr<<"can't open t0 file\n";
        return 1;
    }
    uint32_t tot=0;
    uint32_t border=binNum+3;//w+s
    std::vector<uint32_t>ans;
    while (fin_t0.read(reinterpret_cast<char*>(buffer.data()), buffer.size())&&cnt<border){
        
        if(cnt==position_Vec[pointer].first){
            bool ok = (cnt<binNum)? cuckooP.find(buffer):cuckooS.find(buffer);
           
            if(ok){//找到一个
                ans.push_back(position_Vec[pointer].second);
                tot++;
            }
            pointer++;
            if(pointer==maxNum)//元素查找完毕
                break;
        }
        cnt++;
    }
    fin_t0.close();
    std::sort(ans.begin(),ans.end());
    std::ifstream inputFile(data_path);      // 打开输入文件
    std::ofstream outputFile(result_path);    // 打开输出文件

    if (!inputFile.is_open()) {
        std::cerr << "无法打开输入文件！" << std::endl;
        return 1;
    }

    if (!outputFile.is_open()) {
        std::cerr << "无法打开输出文件！" << std::endl;
        return 1;
    }
    cnt=1;
    pointer=0;
    std::string line;
    while (std::getline(inputFile, line)&&pointer<tot) {
        if(cnt==ans[pointer]){
             outputFile << line << '\n';  // 将读取的行写入输出文件    
             pointer++;    
        } 
        cnt++;
    }
    std::cout<<cuckooP.get_N()<<" "<<cuckooS.get_N()<<"\n";
    std::cout<<tot<<" elements are in common \n";
    return 0;
}